{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Swaps to Make Strings Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSwap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交换字符使得字符串相同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两个长度相同的字符串&nbsp;<code>s1</code> 和&nbsp;<code>s2</code>，且它们其中&nbsp;<strong>只含有</strong>&nbsp;字符&nbsp;<code>\"x\"</code> 和&nbsp;<code>\"y\"</code>，你需要通过「交换字符」的方式使这两个字符串相同。</p>\n",
    "\n",
    "<p>每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。</p>\n",
    "\n",
    "<p>交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换&nbsp;<code>s1[i]</code> 和&nbsp;<code>s2[j]</code>，但不能交换&nbsp;<code>s1[i]</code> 和&nbsp;<code>s1[j]</code>。</p>\n",
    "\n",
    "<p>最后，请你返回使 <code>s1</code> 和 <code>s2</code> 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回&nbsp;<code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"xx\", s2 = \"yy\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：\n",
    "</strong>交换 s1[0] 和 s2[1]，得到 s1 = \"yx\"，s2 = \"yx\"。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"xy\", s2 = \"yx\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：\n",
    "</strong>交换 s1[0] 和 s2[0]，得到 s1 = \"yy\"，s2 = \"xx\" 。\n",
    "交换 s1[0] 和 s2[1]，得到 s1 = \"xy\"，s2 = \"xy\" 。\n",
    "注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 \"yx\"，因为我们只能交换属于两个不同字符串的字符。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"xx\", s2 = \"xy\"\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length, s2.length &lt;= 1000</code></li>\n",
    "\t<li><code>s1.length == s2.length</code></li>\n",
    "\t<li><code>s1, s2</code>&nbsp;只包含&nbsp;<code>'x'</code>&nbsp;或&nbsp;<code>'y'</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-swaps-to-make-strings-equal](https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-swaps-to-make-strings-equal](https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"xx\"\\n\"yy\"', '\"xy\"\\n\"yx\"', '\"xx\"\\n\"xy\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        return -1 if d & 1 else d // 2 + cnt['x'] % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        return -1 if d % 2 else d // 2 + cnt['x'] % 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt.total()\n",
    "        return -1 if d & 1 else d // 2 + cnt['x'] % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        N = len(s1)\n",
    "\n",
    "        # 统计两字符串中不同的情况\n",
    "        count1 = 0\n",
    "        count2 = 0\n",
    "        for i in range(N):\n",
    "            ch1 = s1[i]\n",
    "            ch2 = s2[i]\n",
    "            if ch1 == \"x\" and ch2 == \"y\":\n",
    "                count1 += 1\n",
    "            elif ch1 == \"y\" and ch2 == \"x\":\n",
    "                count2 += 1\n",
    "\n",
    "        a1, b1 = divmod(count1, 2)\n",
    "        a2, b2 = divmod(count2, 2)\n",
    "\n",
    "        # 判断两字符串是否可交换生成\n",
    "        if b1 + b2 != 1:\n",
    "            return a1 + a2 + b1 + b2\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        xydict={'yx':0,'xy':0}\n",
    "        for i in range(n):\n",
    "            a = s1[i]+s2[i]\n",
    "            if a in ['xy','yx']:\n",
    "                xydict[a] += 1\n",
    "        print(xydict)\n",
    "        if (xydict['yx']+xydict['xy'])%2 != 0:\n",
    "            return -1\n",
    "        return xydict['yx']//2 + xydict['yx']%2+xydict['xy']//2 + xydict['xy']%2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy,yx=0,0\n",
    "        n=len(s1)\n",
    "        for a,b in zip(s1,s2):\n",
    "            if a=='x' and b=='y':\n",
    "                xy+=1\n",
    "            if a=='y' and b=='x':\n",
    "                yx+=1\n",
    "        if(xy+yx)%2==1:\n",
    "            return -1\n",
    "        return xy//2+yx//2+xy%2+yx%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        return -1 if d % 2 else d // 2 + cnt['x'] % 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        # 首先判断x和y的个数\n",
    "        if (s1.count(\"x\") + s2.count(\"x\")) % 2 == 1 or (s1.count(\"y\") + s2.count(\"y\")) % 2 == 1:\n",
    "            return -1\n",
    "        result = 0\n",
    "        n = len(s1)\n",
    "        # 统计不同地方x和y的个数\n",
    "        x_num,y_num = 0,0\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == \"x\":\n",
    "                    x_num += 1\n",
    "                else:\n",
    "                    y_num += 1\n",
    "        # 找出其中最大值\n",
    "        if x_num % 2 == 1:\n",
    "            return (x_num + y_num) // 2 + 1\n",
    "        else:\n",
    "            return (x_num + y_num) // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cntX = s1.count('x') + s2.count('x')\n",
    "        if cntX & 1:\n",
    "            return -1\n",
    "        \n",
    "        xy = yx = 0\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            if c1 == c2:\n",
    "                continue\n",
    "            if c1 == 'x':\n",
    "                xy += 1\n",
    "            else:\n",
    "                yx += 1\n",
    "        return xy // 2 + yx // 2 + (xy & 1) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        numXY, numYX = 0, 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i] and s1[i] == 'x':\n",
    "                numXY += 1\n",
    "            elif s1[i] != s2[i] and s2[i] == 'x':\n",
    "                    numYX += 1\n",
    "        if (numXY+numYX) % 2 == 1:\n",
    "            return -1\n",
    "        ret = (numXY+numYX)//2\n",
    "        if numXY % 2 == 1:\n",
    "            ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx = 0, 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            elif s1[i] == \"x\" and s2[i] == \"y\":\n",
    "                xy += 1\n",
    "            else:\n",
    "                yx += 1\n",
    "        \n",
    "        if (xy + yx) & 1 == 1:\n",
    "            return -1\n",
    "        print(xy & 1, yx & 1)\n",
    "        return xy // 2 + yx // 2 + (xy & 1) + (yx & 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx = 0, 0\n",
    "        n = len(s1)\n",
    "        for a, b in zip(s1, s2):\n",
    "            if a == 'x' and b == 'y':\n",
    "                xy += 1\n",
    "            if a == 'y' and b == 'x':\n",
    "                yx += 1\n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + xy % 2 + yx % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy = 0\n",
    "        yx = 0\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            if c1 == \"x\" and c2 == \"y\":\n",
    "                xy += 1\n",
    "            elif c1 == \"y\" and c2 == \"x\":\n",
    "                yx += 1\n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + xy % 2 + yx % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        xy , yx = 0 , 0 \n",
    "        for i in range(n):\n",
    "            if s1[i] == \"x\" and s2[i] == \"y\":\n",
    "                xy += 1\n",
    "            if s1[i] == \"y\" and s2[i] == \"x\":\n",
    "                yx += 1\n",
    "        if (xy + yx) & 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + xy % 2 + yx % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        \n",
    "        xy = 0\n",
    "        yx = 0\n",
    "        for i in range(n):\n",
    "            if s1[i] == 'x' and s2[i] =='y':\n",
    "                xy += 1\n",
    "            elif s1[i] == 'y' and s2[i] == 'x':\n",
    "                yx += 1\n",
    "            else:\n",
    "                pass\n",
    "        \n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return xy // 2 + yx // 2 + xy % 2 + yx % 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        new_s1 = ''\n",
    "        new_s2 = ''\n",
    "        for i in range(n):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            new_s1 += s1[i]\n",
    "            new_s2 += s2[i]\n",
    "        \n",
    "        n2 = len(new_s1)\n",
    "        if n2 % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        cnt_x, cnt_y = 0, 0\n",
    "        for c in new_s1:\n",
    "            if c == 'x':\n",
    "                cnt_x += 1\n",
    "            else:\n",
    "                cnt_y += 1\n",
    "        res = cnt_x // 2 + cnt_x % 2 + cnt_y // 2 + cnt_y % 2\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy = 0\n",
    "        yx = 0\n",
    "\n",
    "        for x,y in zip(s1,s2):\n",
    "            if x == y:\n",
    "                continue\n",
    "            if x == 'x' and y == 'y':\n",
    "                xy += 1\n",
    "            if x == 'y' and y == 'x':\n",
    "                yx += 1\n",
    "        if (xy+yx)%2 == 1:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        ans += xy//2\n",
    "        ans += yx //2\n",
    "        if xy%2 == 1:\n",
    "            ans += 2\n",
    "        return ans \n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1, s2):\n",
    "        #让人觉得奇怪啊，要交换次数最少，有几个位置对不上就一定要有多少次吧\n",
    "        #哦，交换的最优解就是换一次对上位两个\n",
    "        #那岂不是我们直接统计s1的有多少对不上\n",
    "        #对上的位置肯定不能用来交换，对不上的每次要x, x或y, y互相对着换一个，如果有多的x或y没对上就会寄 \n",
    "        xErrorCnt = 0\n",
    "        yErrorCnt = 0\n",
    "        for m, n in zip(s1, s2):\n",
    "            if m == n:\n",
    "                continue\n",
    "            if m == 'x':\n",
    "                xErrorCnt += 1\n",
    "            elif m == 'y':\n",
    "                yErrorCnt += 1\n",
    "        if xErrorCnt % 2 != yErrorCnt % 2:\n",
    "            return -1\n",
    "        else:\n",
    "            if xErrorCnt % 2 == 0:\n",
    "                return (xErrorCnt + yErrorCnt) // 2\n",
    "            else:\n",
    "                return (xErrorCnt + yErrorCnt) // 2 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        stack = []\n",
    "        swap = 0\n",
    "        d = 0\n",
    "        s_x = 0\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                d += 1\n",
    "                if s1[i] == 'x': s_x += 1\n",
    "        if d%2 != 0: return -1\n",
    "        return d//2 if s_x%2==0 else d//2+1\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy = yx = 0\n",
    "        for a, b in zip(s1, s2):\n",
    "            if a == 'x' and b == 'y':\n",
    "                xy += 1\n",
    "            if a == 'y' and b == 'x':\n",
    "                yx += 1\n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + xy % 2 + yx % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        if d % 2 != 0:\n",
    "            return -1\n",
    "\n",
    "        return d // 2 + cnt['x'] % 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Greedy. Time O(n) Space O(1)\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        dx, dy = 0, 0\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    dx += 1\n",
    "                else:\n",
    "                    dy += 1\n",
    "        d = dx + dy\n",
    "        if d % 2 == 0:\n",
    "            if dx % 2 == 0:\n",
    "                return d // 2\n",
    "            else:\n",
    "                return d // 2 + 1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx = 0, 0\n",
    "        n = len(s1)\n",
    "        for a, b in zip(s1, s2):\n",
    "            if a == 'x' and b == 'y':\n",
    "                xy += 1\n",
    "            if a == 'y' and b == 'x':\n",
    "                yx += 1\n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + xy % 2 + yx % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        s = s1 + s2\n",
    "        num_x = list(s).count('x')\n",
    "        if num_x % 2 == 1:\n",
    "            return -1\n",
    "\n",
    "        lis_1, lis_2 = list(s1), list(s2)\n",
    "        i = 0\n",
    "        while i < len(lis_1):\n",
    "            if lis_1[i] == lis_2[i]:\n",
    "                lis_1.pop(i)\n",
    "                lis_2.pop(i)\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        res = 0\n",
    "        if lis_1.count('x') % 2 == 0:\n",
    "            res = lis_1.count('x') // 2 + lis_1.count('y') // 2\n",
    "        else:\n",
    "            res = lis_1.count('x') // 2 + lis_1.count('y') // 2 + 2\n",
    "        \n",
    " \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "\n",
    "        def valaid():\n",
    "            numa = 0\n",
    "            numb = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i] == 'x':\n",
    "                    numa = numa + 1\n",
    "                elif s1[i] == 'y':\n",
    "                    numb = numb + 1\n",
    "                if s2[i] == 'x':\n",
    "                    numa = numa + 1\n",
    "                elif s2[i] == 'y':\n",
    "                    numb = numb + 1\n",
    "            if numa % 2 != 0 or numb % 2 != 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        if valaid():\n",
    "            step = 0\n",
    "            s1 = list(s1)\n",
    "            s2 = list(s2)\n",
    "            xy, yx = 0, 0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == 'x' and s2[j] == 'y':\n",
    "                    xy = xy + 1\n",
    "                elif s1[j] == 'y' and s2[j] == 'x':\n",
    "                    yx = yx + 1\n",
    "            return (xy//2 + yx//2) + (xy%2 + yx%2)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        s3 = s1 + s2\n",
    "        if s3.count('x') % 2 or s3.count('y') % 2: return -1\n",
    "        cnt1 = cnt2 = 0\n",
    "        for i, x in enumerate(s1):\n",
    "            if x == s2[i]: continue\n",
    "            if x == 'x': cnt1 += 1\n",
    "            else: cnt2 += 1\n",
    "        \n",
    "        res = cnt1 // 2 + cnt2 // 2\n",
    "        cnt1, cnt2 = cnt1%2, cnt2%2\n",
    "        return res + (cnt1 == 1) * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        ret = 0\n",
    "        xy = yx = 0\n",
    "        for i in range(n):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            else:\n",
    "                if s1[i] == 'x':\n",
    "                    xy += 1\n",
    "                else:\n",
    "                    yx += 1\n",
    "        if (xy + yx) % 2 == 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return xy // 2 + yx // 2 + xy % 2 + yx % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        return -1 if d % 2 else d // 2 + cnt['x'] % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx=0,0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i]=='x' and s2[i]=='y':\n",
    "                xy+=1\n",
    "            elif s1[i]=='y' and s2[i] == 'x':\n",
    "                yx += 1\n",
    "        if xy == 0 and yx==0:\n",
    "            return 0\n",
    "        if (xy+yx)%2==0:\n",
    "            if xy%2!=0:\n",
    "                return xy//2+yx//2+2\n",
    "            else:\n",
    "                return xy//2+yx//2\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\r\n",
    "        m,n = len(s1),len(s2)\r\n",
    "        if m != n:\r\n",
    "            return -1\r\n",
    "        x1,y1 = 0,0\r\n",
    "        for i in range(m):\r\n",
    "            if s1[i] == s2[i]:\r\n",
    "                continue\r\n",
    "            if s1[i] == 'x' and s2[i] == 'y':\r\n",
    "                x1 += 1\r\n",
    "            else:\r\n",
    "                y1 += 1\r\n",
    "        if (x1 + y1) % 2 != 0:\r\n",
    "            return -1\r\n",
    "        return x1 // 2 + y1 // 2 + (x1 % 2) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "\n",
    "        def valaid():\n",
    "            numa = 0\n",
    "            numb = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i] == 'x':\n",
    "                    numa = numa + 1\n",
    "                elif s1[i] == 'y':\n",
    "                    numb = numb + 1\n",
    "                if s2[i] == 'x':\n",
    "                    numa = numa + 1\n",
    "                elif s2[i] == 'y':\n",
    "                    numb = numb + 1\n",
    "            if numa % 2 != 0 or numb % 2 != 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        if valaid():\n",
    "            step = 0\n",
    "            s1 = list(s1)\n",
    "            s2 = list(s2)\n",
    "            xy, yx = 0, 0\n",
    "            for j in range(len(s1)):\n",
    "                if s1[j] == 'x' and s2[j] == 'y':\n",
    "                    xy = xy + 1\n",
    "                elif s1[j] == 'y' and s2[j] == 'x':\n",
    "                    yx = yx + 1\n",
    "            return (xy//2 + yx//2) + (xy%2 + yx%2)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        num_x_s1, num_y_s1 = 0, 0\n",
    "        num_x_s2, num_y_s2 = 0, 0\n",
    "        for c in s1:\n",
    "            if c == 'x':\n",
    "                num_x_s1 += 1\n",
    "            elif c == 'y':\n",
    "                num_y_s1 += 1\n",
    "        for c in s2:\n",
    "            if c == 'x':\n",
    "                num_x_s2 += 1\n",
    "            elif c == 'y':\n",
    "                num_y_s2 += 1\n",
    "        if (num_x_s1 + num_x_s2) % 2 != 0 or (num_y_s1 + num_y_s2) % 2 !=0:\n",
    "            return -1\n",
    "        x_count, y_count = 0, 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    x_count += 1\n",
    "                else:\n",
    "                    y_count += 1\n",
    "        ans = x_count//2 + y_count//2 + x_count%2 + y_count%2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1, s2):\n",
    "        #让人觉得奇怪啊，要交换次数最少，有几个位置对不上就一定要有多少次吧\n",
    "        #哦，交换的最优解就是换一次对上位两个\n",
    "        #那岂不是我们直接统计s1的有多少对不上\n",
    "        #对上的位置肯定不能用来交换，对不上的每次要x, x或y, y互相对着换一个，如果有多的x或y没对上就会寄 \n",
    "        xErrorCnt = 0\n",
    "        yErrorCnt = 0\n",
    "        for m, n in zip(s1, s2):\n",
    "            if m == n:\n",
    "                continue\n",
    "            if m == 'x':\n",
    "                xErrorCnt += 1\n",
    "            elif m == 'y':\n",
    "                yErrorCnt += 1\n",
    "        if xErrorCnt % 2 != yErrorCnt % 2:\n",
    "            return -1\n",
    "        else:\n",
    "            if xErrorCnt % 2 == 0:\n",
    "                return (xErrorCnt + yErrorCnt) // 2\n",
    "            else:\n",
    "                return (xErrorCnt + yErrorCnt) // 2 + 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt.total()\n",
    "        return -1 if d & 1 else d // 2 + cnt['x'] % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        xerr, yerr = 0,0\n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    xerr += 1\n",
    "                else:\n",
    "                    yerr += 1\n",
    "        if not (xerr + yerr)%2==0:\n",
    "            return -1\n",
    "        res = (xerr//2) + (yerr//2)\n",
    "        res += (2 if xerr%2 == 1 else 0) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        # XY XX 失败 不同的奇数组\n",
    "        # XXY XYX  成功 交换两次  XYY XXX -> XXY XXY 奇数个X 奇数个y  d/2 + 1\n",
    "        # XXX XYY  成功 交换一次  XXY XXY  偶数个x 偶数个y   d/2\n",
    "        if s1 == s2:\n",
    "            return 0\n",
    "        sx = 0\n",
    "        sy = 0\n",
    "        d = 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                d += 1\n",
    "                if s1[i] == 'x':\n",
    "                    sx += 1\n",
    "                if s2[i] == 'y':\n",
    "                    sy += 1\n",
    "        if d % 2 != 0:\n",
    "            return -1\n",
    "        else:\n",
    "            if sx % 2 == 0 and sy % 2 == 0:\n",
    "                return d // 2\n",
    "            else:\n",
    "                return d // 2 + 1\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1, s2):\n",
    "        #让人觉得奇怪啊，要交换次数最少，有几个位置对不上就一定要有多少次吧\n",
    "        #哦，交换的最优解就是换一次对上位两个\n",
    "        #那岂不是我们直接统计s1的有多少对不上\n",
    "        #对上的位置肯定不能用来交换，对不上的每次要x, x或y, y互相对着换一个，如果有多的x或y没对上就会寄 \n",
    "        xErrorCnt = 0\n",
    "        yErrorCnt = 0\n",
    "        for m, n in zip(s1, s2):\n",
    "            if m == n:\n",
    "                continue\n",
    "            if m == 'x':\n",
    "                xErrorCnt += 1\n",
    "            elif m == 'y':\n",
    "                yErrorCnt += 1\n",
    "        if xErrorCnt % 2 != yErrorCnt % 2:\n",
    "            return -1\n",
    "        else:\n",
    "            if xErrorCnt % 2 == 0:\n",
    "                return (xErrorCnt + yErrorCnt) // 2\n",
    "            else:\n",
    "                return (xErrorCnt + yErrorCnt) // 2 + 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xu, yu = (0, 0)\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == 'y':\n",
    "                    yu += 1\n",
    "                else:\n",
    "                    xu += 1\n",
    "                    \n",
    "        ans = 0\n",
    "        if (xu + yu) & 1 > 0:\n",
    "            ans = -1\n",
    "        else:\n",
    "            ans = (xu // 2) + (yu // 2) + (xu & 1) + (yu & 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        x = s1.count('x') + s2.count('x')\n",
    "        y = s1.count('y') + s2.count('y')\n",
    "        if x % 2 != 0 or y % 2 != 0:\n",
    "            return -1\n",
    "        count_x, count_y = 0, 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    count_x += 1\n",
    "                else:\n",
    "                    count_y += 1\n",
    "        return count_x // 2 + count_y // 2 + count_x % 2 + count_y % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        # 分别记录s1的在x与y的错误个数，两者之和为奇数则无法相同\n",
    "        # 相同字符的错误，每两个能够通过1次操作消除。若最后剩下1个错误\n",
    "        # 则另一个字符必定也会剩下1个错误，则最后这两个需要两次操作\n",
    "        n = len(s1)\n",
    "        xerr, yerr = 0,0\n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    xerr += 1\n",
    "                else:\n",
    "                    yerr += 1\n",
    "        if not (xerr + yerr)%2==0:\n",
    "            return -1\n",
    "        res = (xerr//2) + (yerr//2)\n",
    "        res += (2 if xerr%2 == 1 else 0) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx = 0, 0\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            elif s1[i] == \"x\" and s2[i] == \"y\":\n",
    "                xy += 1\n",
    "            else:\n",
    "                yx += 1\n",
    "        \n",
    "        if (xy + yx) & 1 == 1:\n",
    "            return -1\n",
    "        return xy // 2 + yx // 2 + (xy & 1) + (yx & 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        # xcot1,ycot1=0,0\n",
    "        # xcot2,ycot2=0,0\n",
    "        # for i in range(n):\n",
    "        #     xcot1 += (1 if s1[i] == 'x' else 0)\n",
    "        #     xcot2 += (1 if s2[i] == 'x' else 0)\n",
    "        #     ycot1 += (1 if s1[i] == 'y' else 0)\n",
    "        #     ycot2 += (1 if s2[i] == 'y' else 0)\n",
    "        # if (xcot1+xcot2)%2==1 or (ycot1+ycot2)%2==1:\n",
    "        #     return -1\n",
    "        xerr, yerr = 0,0\n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    xerr += 1\n",
    "                else:\n",
    "                    yerr += 1\n",
    "        if not (xerr + yerr)%2==0:\n",
    "            return -1\n",
    "        res = (xerr//2) + (yerr//2)\n",
    "        res += (2 if xerr%2 == 1 else 0) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        cnt = Counter(x for x, y in zip(s1, s2) if x != y)\n",
    "        d = cnt['x'] + cnt['y']\n",
    "        return -1 if d % 2 else d // 2 + cnt['x'] % 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        dx, dy = 0, 0\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                if s1[i] == 'x':\n",
    "                    dx += 1\n",
    "                else:\n",
    "                    dy += 1\n",
    "        d = dx + dy\n",
    "        if d % 2 == 0:\n",
    "            if dx % 2 == 0:\n",
    "                return d // 2\n",
    "            else:\n",
    "                return d // 2 + 1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        s=[0,0]\n",
    "        s1=list(s1)\n",
    "        s2=list(s2)\n",
    "        for x,y in zip(s1,s2):\n",
    "            if x!=y:\n",
    "                if x=='x':\n",
    "                    s[0]+=1\n",
    "                else:\n",
    "                    s[1]+=1\n",
    "        if s[0]<s[1]:\n",
    "            s[0],s[1]=s[1],s[0]\n",
    "        res=s[0]-s[1]\n",
    "        if res%2==1:\n",
    "            return -1\n",
    "        res//=2\n",
    "        res+=s[1]+s[1]%2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        xy, yx = 0, 0\n",
    "        for c, t in zip(s1, s2):\n",
    "            if c == 'x' and t == 'y':\n",
    "                xy += 1\n",
    "            if c == 'y' and t == 'x':\n",
    "                yx += 1\n",
    "        if (xy + yx)%2 == 1:\n",
    "            return -1\n",
    "        return xy//2 +yx//2 +xy%2 +yx%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSwap(self, s1: str, s2: str) -> int:\n",
    "        #xxxyxy\n",
    "        #yyxyyx\n",
    "        # c1=Counter(s1)+Counter(s2)\n",
    "        # c0=Counter()\n",
    "        # for c in c1:\n",
    "        #     if c1[c]%2:\n",
    "        #         return -1\n",
    "        xy,yx=0,0\n",
    "        for x,y in zip(s1,s2):\n",
    "            if x==y: continue\n",
    "            if x+y=='xy':\n",
    "                xy+=1\n",
    "            if x+y=='yx':\n",
    "                yx+=1\n",
    "        if (xy+yx)%2: return -1\n",
    "        ans=0\n",
    "        while xy>1:\n",
    "            xy-=2\n",
    "            ans+=1\n",
    "        while yx>1:\n",
    "            yx-=2\n",
    "            ans+=1\n",
    "        if xy or yx:\n",
    "            ans+=2\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
